The most widespread stream encryption method generates an encryption series independently of the message to be encrypted using linear feedback shift registers, to economize on hardware.
The major drawback of linear feedback shift registers is their linearity. In fact, knowing a number of output bits of the register equal to the length of the register, and knowing the feedback polynomial associated with the register, makes it possible to determine the output bits and all subsequent states of the register.
Accordingly, to “break” the linearity of linear feedback shift registers, it is standard practice to combine the outputs of a plurality of registers, and possibly also their internal state, for example using a non-linear Boolean function.
FIG. 7 shows such a generator 100, known as a “shrinking generator”, described in European Patent Application EP 0 619 659, including a first linear feedback shift register 111a, a second linear feedback shift register 111b, and means 112 for selecting the output of the generator 100.
Accordingly, on each shift, the two registers 111a and 111b are shifted simultaneously; the output of the device 100 is equal to the output of the second register 111b if the output of the first register 111a is a 1; otherwise there is no output.
The shrinking generator combines not only the outputs of two linear feedback registers but also, and more generally, any pair of series of bits. The shrinking generator is in a class of stream encryption methods in which one linear feedback register controls another. The idea is to vary the number of shifts firstly between the various registers employed and secondly between two consecutive bits, in order to break the linearity of the registers.
A variant of the shrinking generator known as the “self-shrinking generator” is based on the same principle but uses a single register. The output bits of the register are read two by two; the first bit controls the output of the second so that the output of the system is the second bit if the first is a 1; otherwise there is no output.
Using only linear feedback registers has many drawbacks. The main one is the weakness stemming from the linearity of the device. There are also disadvantages if registers are combined by means of a Boolean function. At the hardware level, these disadvantages stem from the complexity of implementing the function. Moreover, this function is fixed and it is possible to attack it.
Moreover, statistical methods have highlighted certain weaknesses of the shrinking generator and other clock-controlled encryption methods. In particular, in the shrinking generator the number of shifts effected by the two registers between two output bits varies by the same amount for both registers.
Finally, a last drawback of the shrinking generator is its low ratio of the number of output bits to the number of bits computed, which on average is equal to ¼. This ratio is the same for the self-shrinking generator, which has most of the vulnerability of the shrinking generator.